// 版权所有2011 Go作者。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

package ir

// 强连接组件。
// None
// 相互递归函数最小集的运行分析
// 或单个非递归函数，自下而上。
// None
// 查找这些集合就是查找强连接的组件
// 通过静态调用图中的反向拓扑顺序。
// 这样做的算法（称为Tarjan算法）取自
// 塞吉威克，算法，第二版，p。482，有两个调整。
// None
// 首先，不能使用隐藏的闭包函数（n.Func.IsHiddenClosure（））
// 连接组件的根。拒绝使用它作为根
// 强制它进入它出现的函数的组件中。
// 这对于逃逸分析更为方便。
// None
// 第二，每个函数成为图中的两个虚拟节点，
// 使用数字n和n+1。我们将函数的节点号记录为n
// 但是从节点n+1进行搜索。如果搜索告诉我们组件
// 数字（min）是n+1，我们知道这是一个微不足道的组件：一个函数
// 加上它的关闭。如果搜索告诉我们组件编号为
// n、 然后有一条从节点n+1返回到节点n的路径，这意味着
// 函数集是相互递归的。逃逸分析可以是
// 在分析单个非递归函数时比
// 当分析一组相互递归的函数时。

type bottomUpVisitor struct {
	analyze  func([]*Func, bool)
	visitgen uint32
	nodeID   map[*Func]uint32
	stack    []*Func
}

// VisitFuncsBottomUp调用列表中列出的ODCLFUNC节点上的分析。
// 它使用连续的函数组调用analyze，从
// 调用图的底部向上。每次使用调用analyze时
// 函数列表，该列表中的每个函数只调用其他函数
// 在以前调用中传递的一个或多个函数上
// 分析闭包与其外部函数出现在同一列表中。
// 清单尽可能简短，同时保留这些要求。
// （在一个典型的程序中，许多analyze调用只需
// 一个函数。）布尔参数“recursive”传递给analyze
// 指定列表上的函数是否相互递归。
// 如果recursive为false，则列表仅由单个函数及其闭包组成。
// 如果recursive为true，则列表可能仍然只包含一个函数，
// 如果该函数本身是递归的。
func VisitFuncsBottomUp(list []Node, analyze func(list []*Func, recursive bool)) {
	var v bottomUpVisitor
	v.analyze = analyze
	v.nodeID = make(map[*Func]uint32)
	for _, n := range list {
		if n.Op() == ODCLFUNC {
			n := n.(*Func)
			if !n.IsHiddenClosure() {
				v.visit(n)
			}
		}
	}
}

func (v *bottomUpVisitor) visit(n *Func) uint32 {
	if id := v.nodeID[n]; id > 0 {
		// 已经访问
		return id
	}

	v.visitgen++
	id := v.visitgen
	v.nodeID[n] = id
	v.visitgen++
	min := v.visitgen
	v.stack = append(v.stack, n)

	do := func(defn Node) {
		if defn != nil {
			if m := v.visit(defn.(*Func)); m < min {
				min = m
			}
		}
	}

	Visit(n, func(n Node) {
		switch n.Op() {
		case ONAME:
			if n := n.(*Name); n.Class == PFUNC {
				do(n.Defn)
			}
		case ODOTMETH, OCALLPART, OMETHEXPR:
			if fn := MethodExprName(n); fn != nil {
				do(fn.Defn)
			}
		case OCLOSURE:
			n := n.(*ClosureExpr)
			do(n.Func)
		}
	})

	if (min == id || min == id+1) && !n.IsHiddenClosure() {
		// 此节点是强连接组件的根。

		// 传递给VisitDelist的原始min为v.nodeID[n]+1。
		// 如果visitcolist返回到v.nodeID[n]，那么
		// 块是一组相互递归的函数。
		// 否则，它只是一个不递归的单独函数。
		recursive := min == id

		// 从堆栈中删除连接的组件。
		// 标记walkgen，以便将来的访问返回大量
		// 以免影响来电者的最小值。

		var i int
		for i = len(v.stack) - 1; i >= 0; i-- {
			x := v.stack[i]
			if x == n {
				break
			}
			v.nodeID[x] = ^uint32(0)
		}
		v.nodeID[n] = ^uint32(0)
		block := v.stack[i:]
		// 对这组函数运行转义分析。
		v.stack = v.stack[:i]
		v.analyze(block, recursive)
	}

	return min
}
